The last train has long since made it's final trip to Præstø, so you'll either need your own wheels or jump on a bus, which is a fairly infrequent occurrence, so plan ahead.
Buses 78 and 79 runs from Næstved which has frequent train services to Copenhagen. Another, more combersome option from the capital is Bus 91 from Faxe which has train services on the Ãstbanen from Køge which is on the end of the E S-train line. Bus 63 connects with Vordingborg further south on the same railway line as Næstved, so use this if you are heading south towards the islands Lolland-Faster. Line 256 is your choice for going onwards to Møn as it ends in Stege, the islands largest city.
If you have your own wheels, simply follow the Sydmotorvejen motorway E47/E55 to either exit 38 Tappernøje or exit 39 Bårse and turn east, it's well signposted - the former is the most picturesque as it will take you along the fjord.
